package alo.p6.work;

import org.junit.Test;
import alo.p6.BinaryTreeNode;

import java.util.Arrays;
import java.util.HashMap;

/**
 * @ClassName VerticalSumInBinaryTree
 * @Description 树的垂直和
 * @Author Fanxc
 * @DATE 2021/1/31 14:55
 * @Version 1.0
 */
public class VerticalSumInBinaryTree {
    HashMap<Integer,Integer> map=new HashMap<>();
    void verticalSumInBinaryTree(BinaryTreeNode root,int column){
        if (root==null){
            return;
        }
        //左孩子该序列-1，有孩子该序列+1，使用散列表，从而把在一条垂直线上的和求出
        verticalSumInBinaryTree(root.getLeft(),column-1);
        map.put(column,map.containsKey(column)?map.get(column)+root.getData():root.getData());
        verticalSumInBinaryTree(root.getRight(),column+1);
    }
    //按序输出垂直和
    void printMap(HashMap<Integer,Integer> map){
        Object[] key_arr = map.keySet().toArray();
        Arrays.sort(key_arr);
        for  (Object key : key_arr) {
            System.out.print(map.get(key)+" ");
        }
    }
    @Test
    public void test() {
        int[] A = {1, 2, 4, 5, 3, 6, 7};
        int[] B = {4, 2, 5, 1, 6, 3, 7};
        BuildBinaryTree buildBinaryTree = new BuildBinaryTree();
        BinaryTreeNode root = buildBinaryTree.buildBinaryTree(B, A, 0, 6);
        verticalSumInBinaryTree(root,0);
        printMap(map);//4 2 12 3 7
    }
}
